【LeetCode 692】Top K Frequent Words 前K个高频单词

发表于 | 分类于


“The Linux philosophy is “Laugh in the face of danger”.Oops.Wrong One. “Do it yourself”. Yes, that”s it.”
Linux的哲学就是“在危险面前放声大笑”，呵呵，不是这句，应该是“一切靠自己，自力更生”才对。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 *
 * 给一非空的单词列表，返回前 k 个出现次数最多的单词。
 * 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
 *
 * 放到map中按次数排序再按字典序排序
 * 重写比较器，可以这么写Comparator.comparing(Map.Entry<String,Integer>::getValue)
 * 但是感觉不灵活，也不好用
 */
public class leetcode692 {
    public  List<String> topKFrequent (String[] words, int k) {
        if (words.length == 0)
            return null;
        List<String> res = new LinkedList<>();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            if (map.containsKey(words[i]))
                map.put(words[i], map.get(words[i])+1);
            else
                map.put(words[i],1);
        }
        List<Map.Entry<String,Integer>> list = new LinkedList<>(map.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare (Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //次数不相等按次数排序
                if(o1.getValue()!=o2.getValue())
                    return o1.getValue().compareTo(o2.getValue());
                //相等按字典序排序
                else
                    return -o1.getKey().compareTo(o2.getKey());
            }
        });
        for(int i=list.size()-1;k>0;k--,i--){
            res.add(list.get(i).getKey());
        }
        return res;
    }
    public static void main(String []args){
            new leetcode692().topKFrequent(new String[]{ "a", "b","b", "c", "c", "d", "b","d"},1);
    }
}
Thanks!